(1) Field of the Invention
The invention relates to bandwidth reclamation on a Universal Serial Bus. More specifically, the invention relates to reducing the system bus throughput load due to universal serial bus bandwidth reclamation.
(2) Related Art
The Universal Serial Bus (USB) is a half duplex single logical wire which permits relatively high speed serial communication between a host system bus and devices on the USB. The USB permits four types of transfers: isochronous transfers, interrupt transfers, control transfers, and bulk transfers.
Isochronous transactions are characterized by a constant fixed data rate between the USB device and the host. It is used for devices that continuously consume or produce data at a fixed rate such as microphones or speakers. To support this, the USB guarantees that a required maximum data rate can be transferred in each frame. USB does not require that these transactions occur at this maximum rate in every frame. Failed transactions are not retried. Therefore, the data delivery is not guaranteed in isochronous transactions. Moreover, isochronous data structure elements are always retired after execution.
Interrupt transactions are characterized by small spontaneous transfers from a device. Interrupt transactions are used for devices that require predictable service intervals, but do not produce predictable data flow. Like isochronous transactions, interrupt transactions have a guaranteed maximum data rate. Interrupt transactions are retired after limited retries due to data corruption or other errors.
Control transactions are used to provide a control channel from the host to the USB devices through which control, status, and configuration information may flow. Control transfers always consist of a set-up stage and zero or more data stages followed by a status stage. A stage consists of one or more transactions.
Bulk transactions are characterized by guaranteed transmission of data between client and host under relaxed latency requirements. Bulk transactions are typically used for devices such as printers which can tolerate large latencies, but require movement of large amounts of data Interrupt, control, and bulk all have guaranteed delivery. Thus, following the data transfer if an acknowledge is not received, the transaction will be retried at the next opportunity.
The USB transfers data in frames. Every frame is one millisecond long and begins with a start of frame packet The host controller driver can schedule pending transactions with isochronous transactions scheduled first, interrupt transactions next and control and bulk transactions following in turn. USB requires that no more than ninety percent of the frame time be allocated to isochronous and interrupt transactions. Ten percent of each flame must be reserved for control transactions. If, for example, isochronous and interrupt transactions fill up ninety percent of the allocated frame and control transactions fill the remaining ten percent, then no bulk transactions will take place in that frame. Conversely, if during a frame no isochronous transactions are scheduled and no control transactions are pending, bulk transactions are allowed to fill the entire frame. Significantly, if the isochronous and interrupt do not fill their scheduled time, this time may be used for bulk or control transfers. This may occur because scheduling always presumes a worst case transmission characteristic or because there are insufficient transactions of those types to fill the possible 90% allocated. Scheduled transactions which do not follow the worst case profile will result in additional bandwidth available for bulk transactions.
The operations of the USB are generally well known in the art Architectural details and signaling characteristics are explicitly defined in Universal Serial Bus Specification, Version 1.0, Jan. 19, 1996. Similarly, one possible universal host controller interface (UHCI) is defined for the interface between the USB and a host system bus. Details in that interface are set forth in Universal Host Controller Interface Design Guide, Revision 1.1, March 1996.
Transactions allow data transfer over the USB. Some number of transactions are moved over the bus in each frame. A frame schedule is used by the host controller to determine what specific transactions are moved in what frame. Different implementations of host controllers will require different organization and control of frame schedules. FIG. 1 shows the diagram of an example prior art frame schedule. A hardware register 101 provides a base address, and a frame counter 102 provides an offset to create an address 103 of a frame pointer 104 in a frame list 105. Each entry of the frame list 105 includes two additional relevant bits and two unused bits in addition to a frame pointer. A T-bit 107 is used to indicate whether transactions are pending for the frame. A Q-bit 106 indicates whether a frame pointer points to transaction descriptor (TD) or a queue head (QH).
TDs are data structures containing characteristics of the transaction requested on the USB. Even though four types of transfers exist on the USB, all TDs use the same format. Different transfer types are distinguishable by a number of control bits. QHs are data structures to support control bulk, and interrupt transactions. Because data is guaranteed to have reliable delivery, such transactions must be queued to facilitate retries in the event a transaction is unsuccessful or, in the case of control and bulk, must be deferred to a subsequent frame. The QH sits at the top of a chain of TDs corresponding to pending transactions of a particular transfer type. The format of a standard prior art QH is shown as element 116. A QH and any associated TDs is a queue context. A QH with no TDs is an empty queue context and is indicated by setting a T-bit of the QH. QHs contain two pointers, a QH link pointer pointing to the next adjacent QH in the schedule and a queue element link pointer pointing to the first TD in the queue.
In executing the frame schedule, the host controller traverses horizontally through the isochronous TDs conducting corresponding transactions. In FIG. 1, frame pointer 104 points to isochronous TD 108, which in turn is linked to the isochronous TD 109, which is linked to isochronous TD 110. To be a valid schedule, all isochronous transactions and any interrupt transactions must be traversed during less than 90% of the frame time (all isochronous and interrupt transactions scheduled must be completed in the frame). Thus, the host controller driver creates the schedule assuming a worst case transmission rate and does not schedule more than the allowable amount of transactions of these types. To achieve this, isochronous TD 110 contains a link pointer pointing to QH 111 corresponding to pending interrupt transactions. Interrupt QH 111 contains an element link pointer pointing to TD 115. The transfer corresponding to TD 115 is completed before the host controller is allowed to follow the QH link pointer of interrupt QH 111 to control QH 112 which in turn points to bulk QH 113. Bulk QH 113 contains a QH link pointer which points to bulk QH 114. Depending on the system and scheduling priority, control transactions can be executed by following QH Links or queue element limits such that, e.g. one control transaction is attempted before the next QH in the schedule is traversed or all pending control transactions under a QH are attempted (as time permits) before moving to the next QH. The first example is much more common.
If time is available in the frame after isochronous transactions corresponding to TDs 108-110 and the relevant transactions corresponding to interrupt and non-reclaimable control QHs 111, 112 occur, the remaining time will be used for reclaimable control/bulk transactions, corresponding to the TDs under QHs 113 and 114. This would typically take the form of retrieving QH 113 from main memory identifying TD 123, retrieving TD 123 and, subsequently, the data corresponding to TD 123 from main memory and sending that data across the USB. The QH link pointer is then followed to identify QH 114 which is retrieved from main memory, TD 126 is identified and retrieved from main memory, and the data corresponding thereto is retrieved from main memory and transmitted across the bus. QH 114 links back to QH 113 via its QH link pointer. Traversal of QHs continues following the QH link pointer until there is insufficient frame time for another transaction or no TDs remain.
FIG. 2 is a flowchart of how bulk and reclaimable control transactions proceed in a prior art system. At functional block 130, a QH is read from memory. To do this read, the host controller must arbitrate for the system bus and be granted access. The host controller then processes the QH read to extract the element link pointer of the first TD from QH, at functional block 131. The host controller must then arbitrate for the system bus to read the TD from main memory at functional block 132. From the retrieved TD, the host controller extracts the data address field to identify a block of data to be sent over the USB at functional block 133.
At functional block 134, that block of data is read from main memory once the host controller again arbitrates for the system bus and is granted access. The data is stored in FIFOs in the host controller. At functional block 135, the data is transmitted across the USB to the device. If the data transmission is successful, a handshake acknowledge is returned by the device to the host controller. Thus, at decision block 136, a determination is made whether the acknowledge has been received. If an acknowledge had been received, the element link pointer in the QH is advanced to point to the next TD in the queue. If the acknowledge has not been received, the QH element link pointer is not advanced, and it continues to point to the first TD in the queue at the time the attempted transaction was initiated.
A determination is made at, decision block 138, whether there is sufficient time for an additional transfer attempt. If there is insufficient time for an additional transfer attempt, no more attempts will be made until the next frame. Otherwise, at functional block 139, the QH link pointer is extracted to identify the next QH to be read. The host controller arbitrates for the bus and reads the QH (this will be either the next QH in line, if there are any, or assuming a single bulk queue context, the same QH previously read will be re-read). Assuming a case in which a maximum data size for bulk transfers is 64 bytes, approximately eighteen such transfers can occur in an otherwise empty frame. This implies at least 72 arbitrations for the system bus with roughly 2MB of bandwidth devoted to transactions supporting the USB. In many cases, a USB device's ability to supply or consume data will be less than the host controller's ability to supply or accept data. These slow devices cause numerous retries because of the inability to match the speed of the host controller, e.g., a slow device may only be able to accept 10 kilobytes. The effect is that significant amount of system bus bandwidth is squandered on transactions which have no chance of completion.
In view of the foregoing, it would be desirable to be able to throttle the attempts of the host controller to supply data to a slow device to more closely match the speed at which the device is able to consume or provide data.